package leetcode.dynamic_programming;

import java.util.Arrays;

/**
 * 198. 打家劫舍
 * <p>
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
 * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * <p>
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：[1,2,3,1]
 * 输出：4
 * 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 * 偷窃到的最高金额 = 1 + 3 = 4 。
 * <p>
 * 示例 2：
 * <p>
 * 输入：[2,7,9,3,1]
 * 输出：12
 * 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
 * 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 * <p>
 * <p>
 * <p>
 * 提示：
 * <p>
 * 0 <= nums.length <= 100
 * 0 <= nums[i] <= 400
 * <p>
 * 分析：状态定义：考虑偷取[x ,n-1]范围内的房子，
 * 状态转移方程：f0= max{v0+f(2), v1+f3, v2 +f4, vn-3+fn-1}  这是f0 就是说，当我第一次考虑偷取0的时候，下一次可能偷取的是从1 - n-1，进行选一个。。。
 * 当第一个选择偷取 1 的时候下一次需要从 3 - n-1进行考虑。 进行考虑，直到最后一个元素被考虑进去。
 */
public class Solution198 {
    //递归实现
    public int rob(int[] nums) {
        return tryRob(nums, 0);
    }

    //考虑偷取 [index- nums.size())范围的房子
    private int tryRob(int[] nums, int index) {
        if (index >= nums.length) {
            return 0;
        }

        // 考虑偷取index到 nums.length-1 的房子  每次将试图偷的房子金额保存下来
        int res = -1;
        for (int i = index; i <= nums.length - 1; i++) {
            res = Math.max(res, nums[i] + tryRob(nums, index + 2));
        }
        return res;
    }


    //记忆搜索法
    //递归实现
    public int rob2(int[] nums) {
        int n = nums.length;
// memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
        int[] memo = new int[n];
        Arrays.fill(memo, -1);
        return tryRob2(nums, 0, memo);
    }

    //考虑偷取 [index- nums.size())范围的房子
    private int tryRob2(int[] nums, int index, int[] memo) {
        if (index >= nums.length) {
            return 0;
        }

        if (memo[index] != -1) {
            return memo[index];
        }

        // 考虑偷取index到 nums.length-1 的房子  每次将试图偷的房子金额保存下来
        int res = -1;
        for (int i = index; i <= nums.length - 1; i++) {
            res = Math.max(res, nums[i] + tryRob2(nums, i + 2, memo));
        }
        memo[index] = res;
        return res;
    }

    //动态规划
    public int rob3(int[] nums) {
        int n = nums.length;
        // memo[i] 表示考虑抢劫 nums[i...n) 所能获得的最大收益
        int[] memo = new int[n];
        Arrays.fill(memo, -1);
        //使用索引时候一定要防止索引越界
        if (n == 0) {
            return 0;
        }
        //考虑子问题 当只有n-1的时候，就只能选择n-1的房子进行
        memo[n - 1] = nums[n - 1];

        for (int i = n - 2; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                memo[i] = Math.max(memo[i], nums[j] + (j + 2 < n ? memo[j + 2] : 0));
            }
        }
        return memo[0];
    }
}
